package 分类.二维动归;

/**
 * dp定义dp[i][j]为字符串a以i-1下标结尾的字符串与字符串b以j-1下标结尾的字符串的最小编辑距离
 * 删除元素和添加元素一样，转换方程为dp[i][j] = dp[i - 1][j] + 1;dp[i][j] = dp[i][j - 1] + 1
 * 替换元素为dp[i][j] = dp[i - 1][j-1] + 1;
 *
 */
public class 编辑距离 {

    public int minDistance(String word1, String word2) {
       int m=word1.length();
       int n=word2.length();
       int[][] dp=new int[m+1][n+1];
       for (int i=0;i<=m;i++){
           dp[i][0]=i;
       }
        for (int j=0;j<=n;j++){
            dp[0][j]=j;
        }
        for (int i=1;i<=m;i++){
            for (int j=1;j<=n;j++){
              if(word1.charAt(i-1)!=word2.charAt(j-1)){
                  dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
              }else {
                  dp[i][j]=dp[i-1][j-1];
              }
            }
        }
        return dp[m][n];
    }
}
